package summary;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/10 12:28
 * https://leetcode-cn.com/problems/repeated-substring-pattern/
 */
public class Title459 {

    public static boolean repeatedSubstringPattern(String s) {
        int maxLen = getNext(s);
        //数组长度-最长相等前后缀的长度 正好可以被数组的长度整除，说明有该字符串有重复的子字符串。
        return maxLen != 0 && s.length() % (s.length() - maxLen) == 0;
    }

    private static int getNext(String s) {
        int[] next = new int[s.length() + 2];
        int i = 1, j = 0;
        while (i <= s.length()) {
            if (j == 0 || s.charAt(i - 1) == s.charAt(j - 1)) {
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
        return next[s.length() + 1] - 1;
    }

    public static void main(String[] args) {
        repeatedSubstringPattern("abaabaaba");
    }
}
